home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c-part1 / 3021 < prev    next >
Encoding:
Text File  |  1996-08-05  |  1.9 KB  |  54 lines
  1. Newsgroups: comp.lang.c
  2. Path: in1.uu.net!world!mv!usenet
  3. From: ENGR@GSSI.MV.COM (Michael Furman)
  4. Subject: Counting of 1 bits (was: Re: quick decision: is n a power of 2?)
  5. Message-ID: <DLqtBM.87w@mv.mv.com>
  6. Mime-Version: 1.0
  7. Organization: GSSI
  8. Date: Thu, 25 Jan 1996 15:21:21 GMT
  9. References: <AAQgE1nWVS@csg.spb.su> <822516654snz@genesis.demon.co.uk>
  10. X-Newsreader: WinVN 0.93.10
  11. X-Nntp-Posting-Host: gssi.mv.com
  12.  
  13. In article <822516654snz@genesis.demon.co.uk>, fred@genesis.demon.co.uk 
  14. says...
  15. >
  16. >In article <AAQgE1nWVS@csg.spb.su>
  17. >           alex@csg.spb.su "Alexander N. Pryguichev" writes:
  18. >
  19. >>There is well known solution:
  20. >>
  21. >>Boolean IsPowerOfTwo(unsigned long x)
  22. >>{ long y;
  23. >>  y = x & 0x55555555; y += (x >> 1) & 0x55555555;
  24. >>  x = y & 0x33333333; x += (y >> 2) & 0x33333333;
  25. >>  y = x & 0x0F0F0F0F; y += (x >> 4) & 0x0F0F0F0F;
  26. >>  x = y & 0x00FF00FF; x += (y >> 8) & 0x00FF00FF;
  27. >>  y = x & 0x0000FFFF; y += (x >>16) & 0x0000FFFF;
  28. >
  29. >That is a well known method for counting the number of 1 bits in a 32 bit
  30. >value. 
  31.  
  32. Could you please provide some reference for this method. I am jus curious
  33. who was 1-st inventor of that method. I know that it was invented in Russia
  34. by M. Bongard or A. Brudno (I am not sure). And I learned it in about 1966.
  35.  
  36. And by the way, is a simillar metod for transponing a bynary matrix also
  37. well known? 
  38.  
  39. >-- 
  40. >-----------------------------------------
  41. >Lawrence Kirby | fred@genesis.demon.co.uk
  42. >Wilts, England | 70734.126@compuserve.com
  43. >-----------------------------------------
  44.  
  45. -- 
  46. <<<<<<<< This is a copy of post to the newsgroup >>>>>>>>
  47. ---------------------------------------------------------------
  48. Michael Furman,                       (603)893-1109
  49. Geophysical Survey Systems, Inc.  fax:(603)889-3984
  50. 13 Klein Drive - P.O. Box 97          engr@gssi.mv.com 
  51. North Salem, NH 03073-0097            71543.1334@compuserve.com
  52. ---------------------------------------------------------------
  53.  
  54.